#include <iostream>
#include <vector>
using namespace std;

bool isValidSegment(string segment) {
    if (segment.empty() || segment.length() > 3 || (segment.length() > 1 && segment[0] == '0')) {
        return false;
    }

    int num = stoi(segment);
    return num >= 0 && num <= 255;
}

void restoreIpAddress(string s, vector<string>& result, string current, int segments) {
    if (segments == 4 && s.empty()) {
        result.push_back(current);
        return;
    }

    if (segments == 4 || s.empty()) {
        return;
    }

    for (int i = 1; i <= min(3, (int)s.length()); i++) {
        string segment = s.substr(0, i);
        if (isValidSegment(segment)) {
            if (segments == 1) {
                restoreIpAddress(s.substr(i), result, current + segment, segments + 1);
            } else {
                restoreIpAddress(s.substr(i), result, current + segment + ".", segments + 1);
            }
        }
    }
}

vector<string> restoreIpAddresses(string s) {
    vector<string> result;
    if (s.length() < 4 || s.length() > 12) {
        return result;
    }

    restoreIpAddress(s, result, "", 0);
    return result;
}

int main() {
    string s = "25525511135";

    vector<string> result = restoreIpAddresses(s);

    cout << "All possible valid IP addresses from the given string are: " << endl;
    for (string ip : result) {
        cout << ip << endl;
    }

    return 0;
}